import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2022-10-31
 * Time: 22:35
 */
public class Test3 {
    public static void main(String[] args) {
        int []arr = {1,3,5,2,8,4,6,7};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        int low = 0;
        int high = arr.length - 1;
        int mid = (low + high) / 2;
        sort(arr,low,high);
    }
    public static void sort(int[] arr, int low,int high){
        if(low >= high){
            return ;
        }
        int mid = (low + high) / 2;
        sort(arr,low,mid);
        sort(arr,mid + 1,high);
        merge(arr,low,mid,high);
    }
    public static void merge(int []arr,int low,int mid,int high){
        int []temp = new int[high - low + 1];
        int i = 0;
        int left = low;
        int right = mid+1;
        while(left <= mid && right <= high){
            if(arr[left] < arr[right]){
                temp[i++] = arr[left++];
            }else{
                temp[i++] = arr[right++];
            }
        }
        while(left <= mid){
            temp[i++] = arr[left++];
        }
        while(right <= high){
            temp[i++] = arr[right++];
        }
        for (int j = 0; j < i; j++) {
            arr[j+low] = temp[j];
        }
    }
}
